package solution1.demo_2023_10;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class SolutionTree {

    //1.反转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //2.二叉树的最小深度
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        if(root.left == null && root.right != null) {
            return minDepth(root.right) + 1;
        } else if(root.left != null && root.right == null) {
            return minDepth(root.left) + 1;
        } else {
            int left = minDepth(root.left) + 1;
            int right = minDepth(root.right) + 1;
            return Math.min(left, right);
        }
    }

    //3.平衡二叉树
    private int maxPath(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(maxPath(root.left), maxPath(root.right)) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int left = maxPath(root.left);
        int right = maxPath(root.right);
        if(Math.abs(left - right) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    //4.左叶子之和
    private int dfs(TreeNode root, TreeNode prev) {
        if(root == null) {
            return 0;
        }
        if(prev != null && prev.left == root && root.left == null && root.right == null) {
            return root.val;
        }
        return dfs(root.left, root) + dfs(root.right, root);
    }

    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root, null);
    }

}
